//
// Created by Administrator on 2021/7/28.
//
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int minimumJumps(vector<int> &forbidden, int a, int b, int x) {
        // 0代表->,1代表<-
        unordered_set<int> forbid(forbidden.begin(), forbidden.end());
        queue<tuple<int, int, bool>> q;
        q.emplace(0, 0, false);  // 位置  步数  方向
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            int cur = get<0>(p), cnt = get<1>(p), used = get<2>(p);
            if (cur == x)
                return cnt;
            if (cur + a < 6000 and !forbid.count(cur + a)) {
                forbid.insert(cur + a); // 一直向右的可以禁止掉
                q.emplace(cur + a, cnt + 1, false);
            }
            if (!used and cur - b >= 0 and !forbid.count(cur - b)) {
                q.emplace(cur - b, cnt + 1, true);
            }
        }
        return -1;
    }
};

int main() {
    vector<int> forbidden{8, 3, 16, 6, 12, 20};
    Solution solution;
    cout << solution.minimumJumps(forbidden, 15, 13, 11);
    return 0;
}